
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <memory.h>
#include <stdint.h>
#include "_rbtree.h"

#define OFFSETOF(TYPE,MEMBER)((size_t)&((TYPE *)0)->MEMBER)

#define CONTAINER_OF(ptr,type,member)({ \
                                const typeof( ((type *)0)->member) *__mptr = (ptr); \
                                (type *)( (char *)__mptr - OFFSETOF(type,member));})


struct mytype {
    struct rb_node rb_node;
    int key;
};

struct mytype *my_search(struct rb_root *root, int key)
{
    struct rb_node *node = root->rb_node;

    while (node) {
	struct mytype *data = CONTAINER_OF(node, struct mytype, rb_node);

	if (key < data->key)
	    node = node->rb_left;
	else if (key > data->key)
	    node = node->rb_right;
	else
	    return data;
    }
    
    return NULL;
}

int my_insert(struct rb_root *root, struct mytype *data)
{
    struct rb_node **tmp = &(root->rb_node), *parent = NULL;

    /* Figure out where to put new node */
    while (*tmp) {
	struct mytype *this = CONTAINER_OF(*tmp, struct mytype, rb_node);

	parent = *tmp;
	if (data->key < this->key)
	    tmp = &((*tmp)->rb_left);
	else if (data->key > this->key)
	    tmp = &((*tmp)->rb_right);
	else 
	    return -1;
    }
    
    /* Add new node and rebalance tree. */
    rb_link_node(&data->rb_node, parent, tmp);
    rb_insert_color(&data->rb_node, root);
    
    return 0;
}

void my_delete(struct rb_root *root, int key)
{
    struct mytype *data = my_search(root, key);sdsa
    if (!data) { 
	fprintf(stderr, "Not found %d.\n", key);
	return;
    }
    
    rb_erase(&data->rb_node, root);
    free(data);
}

void print_rbtree(struct rb_root *tree)
{
    struct rb_node *node;
    
    
    printf("\n");
}


// int main(int argc, char *argv[])
// {
//     struct rb_root mytree = RB_ROOT;
//     int i, ret, key;
//     struct mytype *tmp;

//     if (argc < 2) {
// 	fprintf(stderr, "Usage: %s key\n", argv[0]);
// 	exit(-1);
//     }

//     key = atoi(argv[1]);

//     printf("Please enter %d integers:\n", key);
//     for (i = 0; i < key; i++) {
// 	tmp = malloc(sizeof(struct mytype));
// 	if (!tmp)
// 	    perror("Allocate dynamic memory");

// 	scanf("%d", &tmp->key);
	
// 	ret = my_insert(&mytree, tmp);
// 	if (ret < 0) {
// 	    fprintf(stderr, "The %d already exists.\n", tmp->key);
// 	    free(tmp);
// 	}
//     }

//     printf("\nthe first test\n");
//     print_rbtree(&mytree);

//     my_delete(&mytree, 21);

//     printf("\nthe second test\n");
//     print_rbtree(&mytree);

//     return 0;
// }



int main(int argc, char *argv[])
{
    struct rb_root mytree = RB_ROOT ;
    struct mytype * myrb_nodes = (struct mytype *)malloc( sizeof(struct mytype)*9999999) ;
    int i = 0 ;
    for( ; i < 9999999 ; i++ )
    {
        myrb_nodes->key = (i + 10)*1245%412 ;
        my_insert(&mytree, &myrb_nodes[i]);        
    }
    
    return 0;
}
